{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Interleaving String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isInterleave"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #交错字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定三个字符串&nbsp;<code>s1</code>、<code>s2</code>、<code>s3</code>，请你帮忙验证&nbsp;<code>s3</code>&nbsp;是否是由&nbsp;<code>s1</code>&nbsp;和&nbsp;<code>s2</code><em> </em><strong>交错 </strong>组成的。</p>\n",
    "\n",
    "<p>两个字符串 <code>s</code> 和 <code>t</code> <strong>交错</strong> 的定义与过程如下，其中每个字符串都会被分割成若干 <strong>非空</strong> 子字符串：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>s = s<sub>1</sub> + s<sub>2</sub> + ... + s<sub>n</sub></code></li>\n",
    "\t<li><code>t = t<sub>1</sub> + t<sub>2</sub> + ... + t<sub>m</sub></code></li>\n",
    "\t<li><code>|n - m| &lt;= 1</code></li>\n",
    "\t<li><strong>交错</strong> 是 <code>s<sub>1</sub> + t<sub>1</sub> + s<sub>2</sub> + t<sub>2</sub> + s<sub>3</sub> + t<sub>3</sub> + ...</code> 或者 <code>t<sub>1</sub> + s<sub>1</sub> + t<sub>2</sub> + s<sub>2</sub> + t<sub>3</sub> + s<sub>3</sub> + ...</code></li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>注意：</strong><code>a + b</code> 意味着字符串 <code>a</code> 和 <code>b</code> 连接。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/02/interleave.jpg\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"aabcc\", s2 = \"dbbca\", s3 = \"aadbbcbcac\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"aabcc\", s2 = \"dbbca\", s3 = \"aadbbbaccc\"\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"\", s2 = \"\", s3 = \"\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= s1.length, s2.length &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= s3.length &lt;= 200</code></li>\n",
    "\t<li><code>s1</code>、<code>s2</code>、和 <code>s3</code> 都由小写英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>您能否仅使用 <code>O(s2.length)</code> 额外的内存空间来解决它?</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [interleaving-string](https://leetcode.cn/problems/interleaving-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [interleaving-string](https://leetcode.cn/problems/interleaving-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aabcc\"\\n\"dbbca\"\\n\"aadbbcbcac\"', '\"aabcc\"\\n\"dbbca\"\\n\"aadbbbaccc\"', '\"\"\\n\"\"\\n\"\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "\n",
    "        if m+n != len(s3):\n",
    "            return False\n",
    "\n",
    "        dp = [[False for _ in range(n+1)] for _ in range(m+1)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]\n",
    "        for j in range(1, n+1):\n",
    "            dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])\n",
    "        return dp[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: 'str', s2: 'str', s3: 'str') -> 'bool':\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1 + n2 != n3:\n",
    "            return False\n",
    "        if n1 == 0:\n",
    "            return s2 == s3\n",
    "        if n2 == 0:\n",
    "            return s1 == s3\n",
    "        \n",
    "        memo = [[False for j in range(n2 + 1)] for i in range(n1 + 1)]\n",
    "        for i in range(n1 + 1):\n",
    "            for j in range(n2 + 1):\n",
    "                if i == 0 and j == 0:\n",
    "                    memo[i][j] = True\n",
    "                elif i == 0:\n",
    "                    memo[i][j] = memo[i][j - 1] and (s2[j - 1] == s3[j - 1])\n",
    "                elif j == 0:\n",
    "                    memo[i][j] = memo[i - 1][j] and (s1[i - 1] == s3[i - 1])\n",
    "                else:\n",
    "                    if s1[i - 1] == s3[i + j - 1]:\n",
    "                        memo[i][j] |= memo[i - 1][j]\n",
    "                    if s2[j - 1] == s3[i + j - 1]:\n",
    "                        memo[i][j] |= memo[i][j - 1]\n",
    "        return memo[-1][-1]\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1, s2, s3):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :type s3: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        memo = {}\n",
    "        def helper(a, b, c):\n",
    "            k = (a, b, c)\n",
    "            if k not in memo:\n",
    "                if len(a) + len(b) != len(c):\n",
    "                    memo[k] = False\n",
    "                elif not a:\n",
    "                    memo[k] = b == c\n",
    "                elif not b:\n",
    "                    memo[k] = a == c\n",
    "                elif a[0] != b[0]:\n",
    "                    if a[0] == c[0]:\n",
    "                        memo[k] = helper(a[1:], b, c[1:])\n",
    "                    elif b[0] == c[0]:\n",
    "                        memo[k] = helper(a, b[1:], c[1:])\n",
    "                    else:\n",
    "                        memo[k] = False\n",
    "                else:\n",
    "                    if a[0] != c[0]:\n",
    "                        memo[k] = False\n",
    "                    else:\n",
    "                        memo[k] = helper(a[1:], b, c[1:]) or helper(a, b[1:], c[1:])\n",
    "            return memo[k]\n",
    "        return helper(s1, s2, s3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1, s2, s3):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :type s3: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        memo = {}\n",
    "        def helper(a, b, c):\n",
    "            k = (a, b, c)\n",
    "            if k not in memo:\n",
    "                if len(a) + len(b) != len(c):\n",
    "                    memo[k] = False\n",
    "                elif not a:\n",
    "                    memo[k] = b == c\n",
    "                elif not b:\n",
    "                    memo[k] = a == c\n",
    "                elif a[0] != c[0] and b[0] != c[0]:\n",
    "                    memo[k] = False\n",
    "                elif a[0] == c[0] and b[0] == c[0]:\n",
    "                    memo[k] = helper(a[1:], b, c[1:]) or helper(a, b[1:], c[1:])\n",
    "                elif a[0] == c[0]:\n",
    "                    memo[k] = helper(a[1:], b, c[1:])\n",
    "                elif b[0] == c[0]:\n",
    "                    memo[k] = helper(a, b[1:], c[1:])\n",
    "            return memo[k]\n",
    "        return helper(s1, s2, s3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1, s2, s3):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :type s3: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        s1,s2,s3 = s3,s2,s1\n",
    "        length1 = len(s1)\n",
    "        length2 = len(s2)\n",
    "        length3 = len(s3)\n",
    "        if not length1 == length2 + length3:\n",
    "            return False\n",
    "        if not s1:\n",
    "            return s2 == s3\n",
    "        elif not s2:\n",
    "            return s1 == s3\n",
    "        elif not s3:\n",
    "            return True\n",
    "        truth1 = [\n",
    "            [False] * (length2 + 1) for i in range(length1 + 1)\n",
    "        ]\n",
    "        truth2 = [\n",
    "            [False] * (length3 + 1) for i in range(length1 + 1)\n",
    "        ]\n",
    "        \n",
    "        truth1[0][0] = truth2[0][0] = True\n",
    "        #here is the computation\n",
    "        for row in range(1,length2 + 1):\n",
    "            truth1[row][row] = truth1[row - 1][row - 1] and s1[row - 1] == s2[row - 1]\n",
    "        for row in range(1,length3 + 1):\n",
    "            truth2[row][row] = truth2[row - 1][row - 1] and s1[row - 1] == s3[row - 1]\n",
    "        for row in range(1,length1 + 1):    #the position of the char in the first string\n",
    "            for col in range(1,min(row,max(length2,length3) + 1)):\n",
    "                if col <= length2:\n",
    "                    truth1[row][col] = (truth1[row - 1][col - 1] and s1[row - 1] == s2[col - 1])\n",
    "                    if row - col <= length3:\n",
    "                        truth1[row][col] = truth1[row][col] or truth2[row - 1][row - col] and s1[row - 1] == s2[col - 1]\n",
    "                \n",
    "                if col <= length3:\n",
    "                    truth2[row][col] = truth2[row - 1][col - 1] and s1[row - 1] == s3[col - 1]\n",
    "                    if row - col <= length2:\n",
    "                        truth2[row][col] = truth2[row][col] or truth1[row - 1][row - col] and s1[row - 1] == s3[col - 1]\n",
    "        return any(truth1[-1]) or any(truth2[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1, s2, s3):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :type s3: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        l1,l2,l3 = len(s1),len(s2),len(s3)\n",
    "        if l3-l2-l1:\n",
    "            return False\n",
    "        matrix = [[False]*(l2+1) for _ in range(l1+1)]\n",
    "        matrix[0][0] = True\n",
    "        for i in range(1,l1+1):\n",
    "            matrix[i][0] = (s1[i-1] is s3[i-1]) and matrix[i-1][0]\n",
    "            if not matrix[i][0]:\n",
    "                break\n",
    "        for i in range(1,l2+1):\n",
    "            matrix[0][i] = (s2[i-1] is s3[i-1]) and matrix[0][i-1]\n",
    "            if not matrix[0][i]:\n",
    "                break\n",
    "        for i in range(1,l1+1):\n",
    "            for j in range(1,l2+1):\n",
    "                matrix[i][j] = (s1[i-1] is s3[i+j-1] and matrix[i-1][j]) or (s2[j-1] is s3[i+j-1] and matrix[i][j-1])\n",
    "        return matrix[l1][l2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: 'str', s2: 'str', s3: 'str') -> 'bool':\n",
    "        if len(s1) + len(s2) != len(s3):\n",
    "            return False\n",
    "        if len(s1) == 0:\n",
    "            return True if s2 == s3 else False\n",
    "        if len(s2) == 0:\n",
    "            return True if s1 == s3 else False\n",
    "        dp = [[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(len(s2)):\n",
    "            if dp[0][i] == 1 and s2[i] == s3[i]:\n",
    "                print(\"s2 \", i)\n",
    "                dp[0][i+1] = 1\n",
    "        for i in range(1, len(s1)+1):\n",
    "            for j in range(len(s2)+1):\n",
    "                if j == 0:\n",
    "                    if dp[i-1][0] == 1 and s1[i-1] == s3[i-1]:\n",
    "                        print(\"s1\", i)\n",
    "                        dp[i][0] = 1\n",
    "                else:\n",
    "                    if dp[i-1][j] == 1:\n",
    "                        if s1[i-1] == s3[i+j-1]:\n",
    "                            print(\"dp \", i, j)\n",
    "                            dp[i][j] = 1\n",
    "                    if dp[i][j-1] == 1:\n",
    "                        if s2[j-1] == s3[i+j-1]:\n",
    "                            print(\"dp \",i,j)\n",
    "                            dp[i][j] = 1\n",
    "        return True if dp[-1][-1]==1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1, s2, s3):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :type s3: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if s1 == s2 == s3 == \"\":\n",
    "            return True\n",
    "\n",
    "        if len(s1) + len(s2) != len(s3):\n",
    "            return False\n",
    "\n",
    "        # 初始化矩阵\n",
    "        matrix = []\n",
    "        for i in range(len(s1) + 1):\n",
    "            matrix.append([False] * (len(s2) + 1))\n",
    "\n",
    "        matrix[0][0] = True\n",
    "\n",
    "        # 初始化边缘\n",
    "        for i in range(1, len(s1) + 1):\n",
    "            matrix[i][0] = (matrix[i - 1][0] and (s1[i - 1] == s3[i - 1]))\n",
    "\n",
    "        for j in range(1, len(s2) + 1):\n",
    "            matrix[0][j] = (matrix[0][j - 1] and (s2[j - 1] == s3[j - 1]))\n",
    "\n",
    "        # 循环计算每个节点是否可达\n",
    "        for i in range(1, len(s1) + 1):\n",
    "            for j in range(1, len(s2) + 1):\n",
    "                top = matrix[i - 1][j] and s1[i - 1] == s3[i - 1 + j]\n",
    "                left = matrix[i][j - 1] and s2[j - 1] == s3[j - 1 + i]\n",
    "                matrix[i][j] = top or left\n",
    "\n",
    "        return matrix[len(s1)][len(s2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import pprint\n",
    "from pprint import pprint\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1, s2, s3):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :type s3: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        s1Len = len(s1)\n",
    "        s2Len = len(s2)\n",
    "        s3Len = len(s3)\n",
    "        \n",
    "        if s1Len + s2Len != s3Len:\n",
    "            return False\n",
    "        dp = [[False for __ in range(s2Len + 1)] for __ in range(s1Len + 1)]\n",
    "        dp[0][0] = True\n",
    "        \n",
    "        for i in range(1, s1Len + 1):\n",
    "            dp[i][0] = True if dp[i - 1][0] and s1[i - 1] == s3[i - 1] else False\n",
    "        \n",
    "        for j in range(1, s2Len + 1):\n",
    "            dp[0][j] = True if dp[0][j - 1] and s2[j - 1] == s3[j - 1] else False\n",
    "            \n",
    "        for i in range(1, s1Len + 1):\n",
    "            for j in range(1, s2Len + 1):\n",
    "                if (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1])\\\n",
    "                    or (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]):\n",
    "                    dp[i][j] = True\n",
    "                else:\n",
    "                    dp[i][j] = False\n",
    "        pprint(dp)            \n",
    "        return dp[s1Len][s2Len]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1, s2, s3):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :type s3: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        import collections\n",
    "        num_of_char = collections.Counter(s1+s2)\n",
    "        num_of_char_cmp = collections.Counter(s3)\n",
    "        res = collections.defaultdict(bool)\n",
    "        res[(0,0)] = True\n",
    "        if len(s1)+len(s2) != len(s3):\n",
    "            return False\n",
    "        for char in s3:\n",
    "            if num_of_char[char] != num_of_char_cmp[char]:\n",
    "                return False\n",
    "        i = 0\n",
    "        for j in range(1, len(s2)+1):\n",
    "            if res[(i,j-1)] and s3[i+j-1] == s2[j-1]:\n",
    "                res[(i, j)] = True\n",
    "            else:\n",
    "                break\n",
    "        j = 0\n",
    "        for i in range(1, len(s1)+1):\n",
    "            if res[(i-1, j)] and s3[i+j-1] == s1[i-1]:\n",
    "                res[(i, j)] = True\n",
    "            else:\n",
    "                break\n",
    "        for i in range(1, len(s1)+1):\n",
    "            for j in range(1, len(s2)+1):\n",
    "                if res[(i-1,j)] and s3[i+j-1] == s1[i-1]:\n",
    "                    res[(i,j)] = True\n",
    "                elif res[(i, j-1)] and s3[i+j-1] == s2[j-1]:\n",
    "                    res[(i,j)] = True\n",
    "        return res[(i,j)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1 = len(s1)\n",
    "        n2 = len(s2)\n",
    "        n3 = len(s3)\n",
    "        if n1 + n2 != n3: return False\n",
    "\n",
    "        dp = [[False] * (n2 + 1) for _ in range(n1 + 1)]\n",
    "\n",
    "        dp[0][0] = True\n",
    "        # 第一行\n",
    "        for j in range(1, n2 + 1):\n",
    "            dp[0][j] = (dp[0][j - 1] and s2[j - 1] == s3[j - 1])\n",
    "\n",
    "        # 第一列\n",
    "        for i in range(1, n1 + 1):\n",
    "            dp[i][0] = (dp[i - 1][0] and s1[i - 1] == s3[i - 1])\n",
    "        # print(dp)\n",
    "\n",
    "        for i in range(1, n1 + 1):\n",
    "            for j in range(1, n2 + 1):\n",
    "                dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or (\n",
    "                        dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "        k = len(s3)\n",
    "        if m+n != k:\n",
    "            return False\n",
    "        dp = []\n",
    "        for i in range(m+1):\n",
    "            for j in range(n+1):\n",
    "                if i==0 and j == 0:\n",
    "                    dp.append(True)\n",
    "                elif i == 0:\n",
    "                    if s2[j-1] == s3[i+j-1] and dp[j-1]==True:\n",
    "                        dp.append(True)\n",
    "                    else:\n",
    "                        dp.append(False)\n",
    "                elif j == 0:\n",
    "                    if s1[i-1] == s3[i+j-1] and dp[j] == True:\n",
    "                        dp[j] = True\n",
    "                    else:\n",
    "                        dp[j] = False\n",
    "                else:\n",
    "                    if s1[i-1] == s3[i+j-1] and dp[j] == True:\n",
    "                        dp[j]=True\n",
    "                    elif s2[j-1] == s3[i+j-1] and dp[j-1]==True:\n",
    "                        dp[j]=True\n",
    "                    else:\n",
    "                        dp[j] = False\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        # len1 = len(s1)\n",
    "        # len2 = len(s2)\n",
    "        # len3 = len(s3)\n",
    "        # if (len1 + len2 != len3):\n",
    "        #     return False\n",
    "        # dp = [[False]*(len2+1) for i in range(len1+1)]\n",
    "        # dp[0][0] = True\n",
    "        len1=len(s1)\n",
    "        len2=len(s2)\n",
    "        len3=len(s3)\n",
    "        if(len1+len2!=len3):\n",
    "            return False\n",
    "        dp=[[False]*(len2+1) for i in range(len1+1)]\n",
    "        dp[0][0]=True\n",
    "        for i in range(1,len1+1):\n",
    "            dp[i][0]=(dp[i-1][0] and s1[i-1]==s3[i-1])\n",
    "        for i in range(1,len2+1):\n",
    "            dp[0][i]=(dp[0][i-1] and s2[i-1]==s3[i-1])\n",
    "        # for i in range(1,len1+1):\n",
    "        #     dp[i][0] = (dp[i-1][0] and s1[i-1] == s3[i-1])\n",
    "        # for i in range(1+len2+1):\n",
    "        #     dp[0][i] = (dp[0][i-1] and s2[i-1]==s3[i-1])\n",
    "\n",
    "        for i in range(1,len1+1):\n",
    "            for j in range(1,len2+1):\n",
    "                dp[i][j] = (dp[i][j-1] and s2[j-1]==s3[i+j-1]) or (dp[i-1][j] and s1[i-1] == s3[i+j-1])\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "        # len1=len(s1)\n",
    "        # len2=len(s2)\n",
    "        # len3=len(s3)\n",
    "        # if(len1+len2!=len3):\n",
    "        #     return False\n",
    "        # dp=[[False]*(len2+1) for i in range(len1+1)]\n",
    "        # dp[0][0]=True\n",
    "        # for i in range(1,len1+1):\n",
    "        #     dp[i][0]=(dp[i-1][0] and s1[i-1]==s3[i-1])\n",
    "        # for i in range(1,len2+1):\n",
    "        #     dp[0][i]=(dp[0][i-1] and s2[i-1]==s3[i-1])\n",
    "        # for i in range(1,len1+1):\n",
    "        #     for j in range(1,len2+1):\n",
    "        #         dp[i][j]=(dp[i][j-1] and s2[j-1]==s3[i+j-1]) or (dp[i-1][j] and s1[i-1]==s3[i+j-1])\n",
    "        # return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        # dp[i,j]表示s1[:i]和s2[:j]能否交错组成s3[:i+j]\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1+n2!=n3:\n",
    "            return False\n",
    "        dp = [[0 for _ in range(n2+1)] for _ in range(n1+1)]\n",
    "        for i in range(n1+1):\n",
    "            dp[i][0] = s1[:i]==s3[:i]\n",
    "        for i in range(n2+1):\n",
    "            dp[0][i] = s2[:i]==s3[:i]\n",
    "        for i in range(1,n1+1):\n",
    "            for j in range(1,n2+1):\n",
    "                case1 = s1[i-1]==s3[i+j-1] and dp[i-1][j]\n",
    "                case2 = s2[j-1]==s3[i+j-1] and dp[i][j-1]\n",
    "                dp[i][j] = case1 or case2\n",
    "        return dp[n1][n2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        l1, l2, l3 = len(s1), len(s2), len(s3)\n",
    "        if l1 + l2 != l3:\n",
    "            return False\n",
    "        else:\n",
    "            dp = [False] * (l2 + 1)\n",
    "            dp[0] = True\n",
    "            for i in range(l1 + 1):\n",
    "                for j in range(l2 + 1):\n",
    "                    if i > 0:\n",
    "                        dp[j] = dp[j] and s1[i - 1] == s3[i + j - 1]\n",
    "                    if j > 0:\n",
    "                        dp[j] = dp[j] or (dp[j - 1] and s2[j - 1] == s3[i + j - 1])\n",
    "            return dp[l2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.save = {}\n",
    "\n",
    "    def f(self, s3, s1, s2):\n",
    "        n3 = len(s3)\n",
    "        n1 = len(s1)\n",
    "        n2 = len(s2)\n",
    "        if n1 + n2 != n3:\n",
    "            return False\n",
    "        if n3 == 0:\n",
    "            return n1 == 0 and n2 == 0\n",
    "        k = (n3, n1, n2)\n",
    "        ans = self.save.get(k)\n",
    "        if ans is not None: return ans\n",
    "\n",
    "        if n1 > 0 and s1[-1] == s3[-1] and self.f(s3[:-1], s1[:-1], s2):\n",
    "            self.save[k] = True\n",
    "            return True\n",
    "        if n2 > 0 and s2[-1] == s3[-1] and self.f(s3[:-1], s1, s2[:-1]):\n",
    "            self.save[k] = True\n",
    "            return True\n",
    "        self.save[k] = False\n",
    "        return False\n",
    "\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        return self.f(s3, s1, s2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        len1 = len(s1)\n",
    "        len2 = len(s2)\n",
    "        len3 = len(s3)\n",
    "        if len1+len2!=len3:\n",
    "            return False\n",
    "        dp = [[False]*(len2+1) for _ in range(len1+1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1,len1+1):\n",
    "            dp[i][0] = dp[i-1][0] and s1[i-1]==s3[i-1]\n",
    "        for j in range(1,len2+1):\n",
    "            dp[0][j] = dp[0][j-1] and s2[j-1]==s3[j-1]\n",
    "        for i in range(1,len1+1):\n",
    "            for j in range(1,len2+1):\n",
    "                dp[i][j] = dp[i-1][j] and s1[i-1]==s3[i+j-1] or dp[i][j-1] and s2[j-1] ==s3[i+j-1]\n",
    "        return dp[-1][-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        len1=len(s1)\n",
    "        len2=len(s2)\n",
    "        len3=len(s3)\n",
    "        if len1+len2!=len3:\n",
    "            return False\n",
    "        dp=[[False]*(len2+1) for i in range(len1+1)]\n",
    "        dp[0][0]=True\n",
    "        for i in range(1,len1+1):\n",
    "            dp[i][0]=dp[i-1][0] and s1[i-1]==s3[i-1]\n",
    "        for j in range(1,len2+1):\n",
    "            dp[0][j]=dp[0][j-1] and s2[j-1]==s3[j-1]\n",
    "        for i in range(1,len1+1):\n",
    "            for j in range(1,len2+1):\n",
    "                dp[i][j]=(dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 97. 交错字符串\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if not s1: return s2 == s3\n",
    "        if not s2: return s1 == s3\n",
    "\n",
    "        size1 = len(s1)\n",
    "        size2 = len(s2)\n",
    "        size3 = len(s3)\n",
    "\n",
    "        if size1 + size2 != size3: return False\n",
    "\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dfs(pos1, pos2, pos3):\n",
    "            nonlocal size1\n",
    "            nonlocal size2\n",
    "            nonlocal size3\n",
    "            if pos1 == size1: return s2[pos2:] == s3[pos3:]\n",
    "            if pos2 == size2: return s1[pos1:] == s3[pos3:]\n",
    "\n",
    "            if s1[pos1] == s3[pos3] and s2[pos2] == s3[pos3]:\n",
    "                return dfs(pos1+1, pos2, pos3+1) or dfs(pos1, pos2+1, pos3+1)\n",
    "            elif s1[pos1] == s3[pos3]:\n",
    "                return dfs(pos1+1, pos2, pos3+1)\n",
    "            elif s2[pos2] == s3[pos3]:\n",
    "                return dfs(pos1, pos2+1, pos3+1)\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "\n",
    "        @lru_cache\n",
    "        def f(s1, s2, s3):\n",
    "            if not s3:\n",
    "                return not s1 and not s2\n",
    "            if not s1 and not s2:\n",
    "                return False\n",
    "            if not s1:\n",
    "                return s2[0] == s3[0] and f(s1, s2[1:], s3[1:])\n",
    "            if not s2:\n",
    "                return s1[0] == s3[0] and f(s1[1:], s2, s3[1:])\n",
    "\n",
    "            a, b = False, False\n",
    "            if s1[0] == s3[0]:\n",
    "                a = f(s1[1:], s2, s3[1:])\n",
    "            if s2[0] == s3[0]:\n",
    "                b = f(s1, s2[1:], s3[1:])\n",
    "            return a or b\n",
    "\n",
    "        return f(s1, s2, s3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n = len(s1)\n",
    "        m = len(s2)\n",
    "        k = len(s3)\n",
    "        dp = [[0 for _ in range(k+1)] for _ in range(m+1)]\n",
    "        if n+m!=k:\n",
    "            return False\n",
    "        ok = False\n",
    "        def work(p1,p2,p3):\n",
    "            nonlocal ok\n",
    "            if p3==k:\n",
    "                ok = True\n",
    "                return\n",
    "            if ok or dp[p2][p3]:\n",
    "                return\n",
    "            if p1<n and s1[p1]==s3[p3]:\n",
    "                work(p1+1,p2,p3+1)\n",
    "                dp[p2][p3+1] = 1\n",
    "            if p2<m and s2[p2]==s3[p3]:\n",
    "                work(p1,p2+1,p3+1)\n",
    "                dp[p2+1][p3+1] = 1\n",
    "        work(0,0,0)\n",
    "        return ok\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if not s3: return True\n",
    "        m, n, l = len(s1), len(s2), len(s3)\n",
    "        if (m+n)!=l: return False\n",
    "        # dp[i][j]表示s1前i个字符和s2前j个字符是否能够组成s3的前i+j个字符\n",
    "        # dp = [[False]*(n+1) for _ in range(m+1)]\n",
    "        # # 边界条件\n",
    "        # dp[0][0] = True\n",
    "        # # 状态转移\n",
    "        # for i in range(m+1):\n",
    "        #     for j in range(n+1):\n",
    "        #         if i > 0:\n",
    "        #             dp[i][j] = dp[i-1][j] and s1[i-1]==s3[i+j-1]\n",
    "        #         if j > 0:\n",
    "        #             dp[i][j] = dp[i][j] or (dp[i][j-1] and s2[j-1]==s3[i+j-1])\n",
    "        # return dp[m][n]\n",
    "\n",
    "        # 状态只跟上一行相关，用滚动数组进行空间优化\n",
    "        dp = [False]*(n+1)\n",
    "        dp[0] = True\n",
    "        for i in range(m+1):\n",
    "            for j in range(n+1):\n",
    "                if i > 0:\n",
    "                    dp[j] = dp[j] and s1[i-1]==s3[i+j-1]\n",
    "                if j > 0:\n",
    "                    dp[j] = dp[j] or (dp[j-1] and s2[j-1]==s3[i+j-1])\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        s1_len,s2_len=len(s1),len(s2)\n",
    "        if s1_len+s2_len != len(s3):\n",
    "            return False\n",
    "        dp=[[False]*(s1_len+1) for _ in range(s2_len+1)]\n",
    "        dp[0][0]=True\n",
    "        for i in range(s2_len+1):\n",
    "            for j in range(s1_len+1):\n",
    "                p=i+j-1\n",
    "                if i>0:\n",
    "                    dp[i][j]=dp[i][j] or (dp[i-1][j] and s2[i-1]==s3[p])\n",
    "                if j>0:\n",
    "                    dp[i][j]=dp[i][j] or (dp[i][j-1] and s1[j-1]==s3[p])\n",
    "        return dp[s2_len][s1_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        len1=len(s1)\n",
    "        len2=len(s2)\n",
    "        len3=len(s3)\n",
    "        if(len1+len2!=len3):\n",
    "            return False\n",
    "        dp=[[False]*(len2+1) for i in range(len1+1)]\n",
    "        dp[0][0]=True\n",
    "        for i in range(1,len1+1):\n",
    "            dp[i][0]=(dp[i-1][0] and s1[i-1]==s3[i-1])\n",
    "        for i in range(1,len2+1):\n",
    "            dp[0][i]=(dp[0][i-1] and s2[i-1]==s3[i-1])\n",
    "        for i in range(1,len1+1):\n",
    "            for j in range(1,len2+1):\n",
    "                dp[i][j]=(dp[i][j-1] and s2[j-1]==s3[i+j-1]) or (dp[i-1][j] and s1[i-1]==s3[i+j-1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        len1=len(s1)\n",
    "        len2=len(s2)\n",
    "        len3=len(s3)\n",
    "        if(len1+len2!=len3):\n",
    "            return False\n",
    "        dp=[[False]*(len2+1) for i in range(len1+1)]\n",
    "        dp[0][0]=True\n",
    "        for i in range(1,len1+1):\n",
    "            dp[i][0]=(dp[i-1][0] and s1[i-1]==s3[i-1])\n",
    "        for i in range(1,len2+1):\n",
    "            dp[0][i]=(dp[0][i-1] and s2[i-1]==s3[i-1])\n",
    "        for i in range(1,len1+1):\n",
    "            for j in range(1,len2+1):\n",
    "                dp[i][j]=(dp[i][j-1] and s2[j-1]==s3[i+j-1]) or (dp[i-1][j] and s1[i-1]==s3[i+j-1])\n",
    "        return dp[-1][-1]\n",
    "        \n",
    "# 链接：https://leetcode.cn/problems/interleaving-string/solutions/48146/dong-tai-gui-hua-zhu-xing-jie-shi-python3-by-zhu-3/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if len(s1)+len(s2)!=len(s3):\n",
    "            return False\n",
    "        if len(s1)==0 :\n",
    "            if s2==s3:\n",
    "                return True\n",
    "            return False\n",
    "        if len(s2)==0 :\n",
    "            if s1==s3:\n",
    "                return True\n",
    "            return False\n",
    "        dp=[[0 for i in range(len(s1)+1)] for ii in range(len(s2)+1)]\n",
    "        dp[0][0]=1\n",
    "        for i, ss in enumerate(s2):\n",
    "            if 1:\n",
    "                if s2[i]==s3[i]:\n",
    "                    dp[i+1][0]=1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        for i, ss in enumerate(s1):\n",
    "            if 1:\n",
    "                if s1[i]==s3[i]:\n",
    "                    dp[0][i+1]=1\n",
    "                else:\n",
    "                    break\n",
    "        for i in range(len(s2)+1):\n",
    "            for j in range(len(s1)+1):\n",
    "                if i==0 or j==0:\n",
    "                    continue\n",
    "                if dp[i-1][j]==1 and s2[i-1]==s3[i+j-1]:\n",
    "                    dp[i][j]=1        \n",
    "                if dp[i][j-1]==1 and s1[j-1]==s3[i+j-1]:\n",
    "                    dp[i][j]=1\n",
    "        print(dp)\n",
    "        return dp[len(s2)][len(s1)]==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        ## 双指针，但是如果s1和s2 都可以和s3匹配，选哪个？就需要都试一下，所以动态规划\n",
    "        ## \n",
    "        n1,n2,n=len(s1),len(s2),len(s3)\n",
    "        if n1+n2!=n:\n",
    "            return False\n",
    "        memo=[[-1]*(n2+1) for _ in range(n1+1)]\n",
    "        def dp(i,j):\n",
    "            k=i+j\n",
    "            if k==n:\n",
    "                return True\n",
    "          \n",
    "            if memo[i][j]!=-1:\n",
    "                return memo[i][j]\n",
    "\n",
    "            res=False\n",
    "            if i<n1 and s1[i]==s3[k]:\n",
    "                res=dp(i+1,j)\n",
    "            if j<n2 and s2[j]==s3[k]:\n",
    "                res= res or dp(i,j+1)\n",
    "            memo[i][j]=res\n",
    "            # print(s1[i],s2[j],s3[k],res)\n",
    "            return res\n",
    "        return dp(0,0)\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "#         self.s1_len, self.s2_len, self.s3_len = len(s1), len(s2), len(s3)\n",
    "#         if self.s1_len + self.s2_len != self.s3_len:\n",
    "#             return False\n",
    "\n",
    "#         self.s1, self.s2, self.s3 = s1, s2, s3\n",
    "#         self.cache = {}  # 缓存\n",
    "#         self.build_cache(0, 0)  # 递归构建\n",
    "#         return self.cache[(0, 0)]\n",
    "\n",
    "#     def build_cache(self, s1_idx, s2_idx):\n",
    "#         if (s1_idx, s2_idx) in self.cache:  # 查缓存\n",
    "#             return self.cache[(s1_idx, s2_idx)]\n",
    "\n",
    "#         s3_idx = s1_idx + s2_idx\n",
    "#         if s3_idx == self.s3_len:  # 递归终止\n",
    "#             result = (s1_idx == self.s1_len) and (s2_idx == self.s2_len)\n",
    "#         elif (s1_idx < self.s1_len) and (s2_idx < self.s2_len) and \\\n",
    "#              (self.s1[s1_idx] == self.s2[s2_idx] == self.s3[s3_idx]):\n",
    "#             # s1和s2都与s3对应字符相等\n",
    "#             result = self.build_cache(s1_idx+1, s2_idx) or \\\n",
    "#                      self.build_cache(s1_idx, s2_idx+1)\n",
    "#         elif s1_idx < self.s1_len and self.s1[s1_idx] == self.s3[s3_idx]:\n",
    "#             # s1与s3对应字符相等\n",
    "#             result = self.build_cache(s1_idx+1, s2_idx)\n",
    "#         elif s2_idx < self.s2_len and self.s2[s2_idx] == self.s3[s3_idx]:\n",
    "#             # s2与s3对应字符相等\n",
    "#             result = self.build_cache(s1_idx, s2_idx+1)\n",
    "#         else:\n",
    "#             result = False\n",
    "\n",
    "#         # 记录\n",
    "#         self.cache[(s1_idx, s2_idx)] = result\n",
    "\n",
    "#         return result\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "#         import functools\n",
    "#         n1 = len(s1)\n",
    "#         n2 = len(s2)\n",
    "#         n3 = len(s3)\n",
    "#         @functools.lru_cache(None)\n",
    "#         def helper(i, j, k):\n",
    "#             if i == n1 and j == n2 and k == n3:\n",
    "#                 return True\n",
    "#             if k < n3:\n",
    "#                 if i < n1 and s1[i] == s3[k] and helper(i+1, j, k+1):\n",
    "#                     return True\n",
    "#                 if j < n2 and s2[j] == s3[k] and helper(i, j+1, k+1):\n",
    "#                     return True\n",
    "#             return False\n",
    "#         return helper(0,0,0)\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "#         len1=len(s1)\n",
    "#         len2=len(s2)\n",
    "#         len3=len(s3)\n",
    "#         if(len1+len2!=len3):\n",
    "#             return False\n",
    "#         dp=[[False]*(len2+1) for i in range(len1+1)]\n",
    "#         dp[0][0]=True\n",
    "#         for i in range(1,len1+1):\n",
    "#             dp[i][0]=(dp[i-1][0] and s1[i-1]==s3[i-1])\n",
    "#         for i in range(1,len2+1):\n",
    "#             dp[0][i]=(dp[0][i-1] and s2[i-1]==s3[i-1])\n",
    "#         for i in range(1,len1+1):\n",
    "#             for j in range(1,len2+1):\n",
    "#                 dp[i][j]=(dp[i][j-1] and s2[j-1]==s3[i+j-1]) or (dp[i-1][j] and s1[i-1]==s3[i+j-1])\n",
    "#         return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1 = len(s1)\n",
    "        n2 = len(s2)\n",
    "        if n1 + n2 != len(s3):\n",
    "            return False\n",
    "\n",
    "        dp = [[0] * (n2 + 1) for i in range(2)]\n",
    "        dp[0][0] = 1\n",
    "        \n",
    "        \n",
    "        for i in range(n1 + 1):\n",
    "            for j in range(n2 + 1):\n",
    "                if not i and not j:\n",
    "                    continue\n",
    "                l = i + j\n",
    "                p1 = p2 = False\n",
    "                if i > 0:\n",
    "                    p1 = (s1[i-1] == s3[l - 1] and dp[(i - 1)%2][j])\n",
    "                if j > 0:\n",
    "                    p2 = (s2[j-1] == s3[l - 1] and dp[i%2][j - 1])\n",
    "                dp[i%2][j] = int(p1 or p2)\n",
    "\n",
    "        return bool(dp[n1%2][n2])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        # dp[i][j] 表示s1前i个字符和s2前j个字符能否构成s3的前i+j个字符\n",
    "\n",
    "        n, m, l = len(s1), len(s2), len(s3)\n",
    "        if n + m != l:\n",
    "            return False\n",
    "        dp = [[False] * (m + 1) for _ in range(n + 1)]\n",
    "        dp [0][0] = True\n",
    "        for i in range(1, n + 1):\n",
    "            dp [i][0] = dp [i - 1][0] and s1[i - 1] == s3[i - 1]\n",
    "        for i in range(1, m + 1):\n",
    "            dp [0][i] = dp [0][i - 1] and s2[i - 1] == s3[i - 1]\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                if s1[i-1] == s3[i+j-1] and dp[i-1][j]:\n",
    "                    dp[i][j] = True\n",
    "                if s2[j-1] == s3[i+j-1] and dp[i][j-1]:\n",
    "                    dp[i][j] = True\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        len1=len(s1)\n",
    "        len2=len(s2)\n",
    "        len3=len(s3)\n",
    "        if len1+len2!=len3:\n",
    "            return False\n",
    "        dp=[[False]*(len2+1) for i in range(len1+1)]\n",
    "        dp[0][0]=True\n",
    "        for i in range(1,len1+1):\n",
    "            dp[i][0]=(dp[i-1][0] and s1[i-1]==s3[i-1])\n",
    "        for i in range(1,len2+1):\n",
    "            dp[0][i]=(dp[0][i-1] and s2[i-1]==s3[i-1])\n",
    "        for i in range(1,len1+1):\n",
    "            for j in range(1,len2+1):\n",
    "                dp[i][j]=(dp[i][j-1] and s2[j-1]==s3[i+j-1]) or (dp[i-1][j] and s1[i-1]==s3[i+j-1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "\n",
    "        # Special case\n",
    "        if len(s1) + len(s2) != len(s3):\n",
    "            return False\n",
    "\n",
    "        # Solution: Dynamic Programming\n",
    "\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "\n",
    "        # Step 1: Construct the state-transition matrix\n",
    "        dp = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        # Step 2: Set the initial state\n",
    "        dp[0][0] = True\n",
    "        for j in range(1, n + 1):\n",
    "            dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]\n",
    "\n",
    "        # Step 3: Define the state-transition matrix\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(n + 1):\n",
    "                k = i + j - 1\n",
    "                dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[k])\n",
    "                if not dp[i][j] and j > 0:\n",
    "                    dp[i][j] = dp[i][j - 1] and s2[j - 1] == s3[k]\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        # dp[i][j]：s3[:i+j]是由s1[:i],s2[:j]交错组成的\n",
    "        n, m = len(s1) + 1 ,len(s2) + 1\n",
    "        dp = [[False] * m for _ in range(n)]\n",
    "        if n + m != len(s3) + 2:\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            dp[i][0] = (s3[:i] == s1[:i])\n",
    "        for j in range(m):\n",
    "            dp[0][j] = (s3[:j] == s2[:j])\n",
    "        print(dp)\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                if s1[i-1] == s3[i+j-1] and s2[j-1] == s3[i+j-1]:\n",
    "                    dp[i][j] = (dp[i-1][j] or dp[i][j-1])\n",
    "                elif s1[i-1] == s3[i+j-1]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                elif s2[j-1] == s3[i+j-1]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "        print(dp)\n",
    "        return dp[n-1][m-1]\n",
    "\n",
    "[[True, False, False, False, False, False],\n",
    "[True, False, False, False, False, False],\n",
    "[True, False, False, False, False, False],\n",
    "[False, False, False, False, False, False],\n",
    "[False, False, False, False, False, False],\n",
    "[False, False, False, False, False, False]]\n",
    "\n",
    "[[True, False, False, False, False, False], \n",
    "[True, False, False, False, False, False], \n",
    "[True, False, False, False, False, False],\n",
    "[False, False, False, False, False, False], \n",
    "[False, False, False, False, False, False], \n",
    "[False, False, False, False, False, False]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if len(s3) != len(s1) + len(s2):\n",
    "            return False\n",
    "        n = len(s1)\n",
    "        m = len(s2)\n",
    "        dp = [[False] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(1, m + 1):\n",
    "            if s2[j - 1] == s3[j - 1]:\n",
    "                dp[0][j] = dp[0][j - 1]\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            if s1[i - 1] == s3[i - 1]:\n",
    "                dp[i][0] = dp[i - 1][0]\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                print(i - 1, j - 1, i + j - 1)\n",
    "                if (s1[i - 1] == s3[i + j - 1] and dp[i - 1][j]) or (s2[j - 1] == s3[i + j - 1] and dp[i][j - 1]):\n",
    "                    dp[i][j] = True\n",
    "        print(dp)\n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1 + n2 != n3: return False\n",
    "\n",
    "        @cache\n",
    "        def helper(i, j):\n",
    "            if i == n1 and j == n2:\n",
    "                return True\n",
    "            if i < n1 and s1[i] == s3[i+j] and helper(i+1, j):\n",
    "                return True\n",
    "            if j < n2 and s2[j] == s3[i+j] and helper(i, j+1):\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        return helper(0, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
